/*
 * Copyright (C) 2010-2011 Graz University of Technology, Austria. All Rights reserved. 
 *
 * Contact: Simone Kopeinik <simone.kopeinik@tugraz.at>
 * 	   Graz University of Technology, Knowledge Management Institute, Brückenkopfgasse 1/6, 8020 Graz 	
 * 	   <http://www.kmi.tugraz.at/>
 * 
 * This software is part of the TARGET platform developed by the
 * TARGET EC-funded project www.reachyourtarget.org
 *
 * This software is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, version 3.
 *
 * This software is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
 * GNU General Public License for more details.
 *
 * The GNU General Public License is available at <http://www.gnu.org/licenses/>.
 *
 */
package at.tugraz.kmi.css.cbkst2.prereq;

import java.util.ArrayList;
import java.util.Collection;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import java.util.logging.Logger;

import at.tugraz.kmi.css.cbkst2.CbKSTVertex;
import at.tugraz.kmi.css.cbkst2.PrerequesiteRelation;

import com.google.inject.Inject;
import com.google.inject.Provider;

import edu.uci.ics.jung.graph.util.EdgeType;
import edu.uci.ics.jung.graph.util.Pair;

final class TransitiveClosureGraph<V extends CbKSTVertex, E extends PrerequesiteRelation>
		extends DirectedAcyclicGraph<V, E> {

	private static final long									serialVersionUID	= 1L;

	private transient final TransitiveClosureCalculator<V, E>	closure;

	private transient final Logger								logger;

	@Inject
	TransitiveClosureGraph(Provider<E> edgeFactory, Logger log) {
		this.closure = new TransitiveClosureCalculator<V, E>(
				new FactoryAdapter<E>(edgeFactory));
		this.logger = log;
	}

	@Override
	public E findEdge(V v1, V v2) {
		return super.findEdge(v1, v2);
	};

	@Override
	public boolean addEdge(E edge, Pair<? extends V> endpoints,
			EdgeType edgeType) {
		boolean addEdge = super.addEdge(edge, endpoints, edgeType);
		if (addEdge) {
			this.closure.closeSimpleDirectedGraph(this);
		}
		return addEdge;
	}

	@Override
	public boolean removeVertex(V v) {
		boolean removeVertex = super.removeVertex(v);
		this.closure.closeSimpleDirectedGraph(this);
		return removeVertex;
	}

	@Override
	public boolean removeEdge(E edge) {
		V dest = getDest(edge);
		V source = getSource(edge);
		// boolean removeEdge = super.removeEdge(edge);

		removeEdges(source, dest, true);
		removeEdges(source, dest, false);

		return super.removeEdge(edge);
	}

	// Do a BFS search to update
	private void removeEdges(V source, V target, boolean incoming) {
		List<V> currentVertices = new ArrayList<V>();
		Set<V> visitedVertices = new HashSet<V>();
		Set<PrerequesiteRelation> visitedEdges = new HashSet<PrerequesiteRelation>();
		Set<V> acceptedVertices = new HashSet<V>();
		Set<E> edgesToBeRemoved = new HashSet<E>();

		// Copy, mark, and add all the root nodes to the new subgraph
		if (incoming) {
			visitedVertices.add(source);
			acceptedVertices.add(source);
			currentVertices.add(source);
		} else {
			visitedVertices.add(target);
			acceptedVertices.add(target);
			currentVertices.add(target);
		}

		ArrayList<V> newVertices = null;
		int currentDepth = 0;
		while (currentDepth < getVertexCount()) {
			newVertices = new ArrayList<V>();
			for (V currentVertex : currentVertices) {

				Collection<E> edges = null;
				if (incoming) {
					edges = getInEdges(currentVertex);
				} else {
					edges = getOutEdges(currentVertex);
				}
				if (edges != null) {
					for (E currentEdge : edges) {

						V currentNeighbor = getOpposite(currentVertex,
								currentEdge);
						if (!visitedEdges.contains(currentEdge)) {
							visitedEdges.add(currentEdge);
							if (!visitedVertices.contains(currentNeighbor)) {
								visitedVertices.add(currentNeighbor);
								E edge = null;
								if (incoming) {
									edge = findEdge(currentNeighbor, target);
								} else {
									edge = findEdge(source, currentNeighbor);
								}
								if (edge != null) {
									edgesToBeRemoved.add(edge);
								}
								acceptedVertices.add(currentNeighbor);
								newVertices.add(currentNeighbor);
							}
						}
					}
				}
			}
			currentVertices = newVertices;
			currentDepth++;
		}

		for (E e : edgesToBeRemoved) {
			this.removeEdge(e);
		}

	}

	public void calcClosure() {
		logger.fine("Calculation Transitive Closure");
		this.closure.closeSimpleDirectedGraph(this);
	}

}
